A double-linked list is a list of items, where each of the items is stored somewhere in a computer memory system. Each item includes a Next pointer to a storage location of a next item in the list, and a Prey pointer to a storage location of a previous item in the list. These two pointers allow traversal of the list in either direction. In a multi-threaded environment, insertion and deletion of list items are most-commonly implemented using locking techniques such as mutual exclusion, which suffer from deadlocks and priority inversion.
Lock-free techniques improve concurrency and scalability by addressing potential issues such as race conditions and deadlocks. Some conventional lock-free techniques manipulate items within double-linked lists by using the compare-and-swap atomic primitive. These techniques are useful if the lists are accessed only via their head or tail nodes. However, these techniques are insufficient if each node in a list is treated as an independent object with any number of possible handles in concurrent threads.